package org.example.myleet.p864;

import java.util.*;

public class Solution {

    private static final int[][] DIR = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int sr = 0, sc = 0;
        //记录每个钥匙对应的位置
        int[] keyToIndex = new int[26];
        Arrays.fill(keyToIndex, -1);
        int keyIdx = -1;
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                char ch = grid[r].charAt(c);
                if (ch == '@') {
                    //找到起点
                    sr = r;
                    sc = c;
                } else if (Character.isLowerCase(ch)) {
                    //找到钥匙，并给每个钥匙定个位置
                    if (keyToIndex[ch - 'a'] < 1) {
                        keyToIndex[ch - 'a'] = ++keyIdx;
                    }
                }
            }
        }
        //动态规划，保存每个点到达每个状态的最小步数，从0~11111...
        int[][][] dp = new int[m][n][1 << (keyIdx + 1)];
        //终点就是拥有全部钥匙，都是1的状态（11111...）
        int end = (1 << (keyIdx + 1)) - 1;
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                //初始化每个状态的步数为-1，即未到达过
                Arrays.fill(dp[r][c], -1);
            }
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc, 0});
        dp[sr][sc][0] = 0;
        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            int r = p[0], c = p[1], status = p[2];
            for (int j = 0; j < 4; ++j) {
                int nr = p[0] + DIR[j][0];
                int nc = p[1] + DIR[j][1];
                if (0 <= nr && nr < m && 0 <= nc && nc < n) {
                    char cha = grid[nr].charAt(nc);
                    if (cha != '#') {
                        if (cha == '.' || cha == '@') {
                            if (dp[nr][nc][status] == -1) {
                                //位置可以走，走一步，状态不变
                                dp[nr][nc][status] = dp[r][c][status] + 1;
                                queue.offer(new int[]{nr, nc, status});
                            }
                        } else if (Character.isLowerCase(cha)) {
                            //找到一个钥匙，获得钥匙的位置
                            int idx = keyToIndex[cha - 'a'];
                            //newStatus是当前拥有钥匙再加一把钥匙的状态
                            int newStatus = status | (1 << idx);
                            if (dp[nr][nc][newStatus] == -1) {
                                //如果当前拥有钥匙的状态还未到达过，那+1就是最短距离
                                dp[nr][nc][newStatus] = dp[r][c][status] + 1;
                                if (newStatus == end) {
                                    //如果已经获取到所有钥匙
                                    return dp[nr][nc][newStatus];
                                }
                                queue.offer(new int[]{nr, nc, newStatus});
                            }
                        } else {
                            //找到一个锁，找对应钥匙的位置
                            int idx = keyToIndex[cha - 'A'];
                            //看看钥匙在当前状态下是否已经获得
                            boolean hasKey = (status & (1 << idx)) != 0;
                            if (hasKey && dp[nr][nc][status] == -1) {
                                //已经获得钥匙的情况下可以走这一步
                                dp[nr][nc][status] = dp[r][c][status] + 1;
                                queue.offer(new int[]{nr, nc, status});
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
}
